package 动态规划;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class Solution338 {

    public static void main(String[] args) {
//        int[] nums = new int[]{7, 1, 5, 3, 6, 4};
//        System.out.println(process(4));
        System.out.println(Arrays.toString(countBits(5)));
        System.out.println(Arrays.toString(dp(5)));
    }

    public static int[] countBits(int n) {
        int[] nums = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            nums[i] = process(i);
        }
        return nums;
    }

    //含义：获取n的二进制1的个数
    public static int process(int n) {
//        HashMap<Integer, Integer> objects = new HashMap<>();
        int[] ans = new int[n + 1];
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n % 2 == 0) {
            //偶数1的个数=偶数/2的1的个数

            return process(n / 2);
        } else {
            //奇数1的个数=奇数/2+1
            return process(n / 2) + 1;
        }
    }

    //dp
    public static int[] dp(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        if (n <= 0) {
            return dp;
        }
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            if (i % 2 == 0) {
                dp[i] = dp[i / 2];
            } else {
                dp[i] = dp[i / 2] + 1;
            }
        }
        return dp;
    }

}
